\section{Appendix~\ref{app:s:3locations}: Proofs Missing from Section~\ref{s:3locations}}
\label{app:s:3locations}

\subsection{A Detailed Proof of Lemma~\ref{l:any-partition}}
\label{app:s:any-partition}

%Let $\vec{x} = (x_1\sep N_1, x_2\sep N_2, x_3\sep N_3)$ be a $3$-location instance such that $x_1 < x_2 < x_3$, $|N_2| \leq n-3$, and $x_2 \in F(\vec{x})$.
%
We consider any $3$-location instance $\vec{y} = (y_1\sep N'_1, y_2\sep N'_2, y_3\sep N'_3)$ with $N'_2 \supseteq N_2$, and show that $y_2 \in F(\vec{y})$.
%
We start with the case where $y_1 < y_3$. By the hypothesis about the existence of $\vec{x}$, and by Corollary~\ref{cor:3agents}, $F$ allocates a facility to the coalition $N_2$ for any instance $(y_1\sep N_1, y_2\sep N_2, y_3\sep N_3)$ with $y_1 < y_3$. In particular, the existence of $\vec{x}$, where the middle coalition $N_2$ is allocated a facility, implies that $N_2$ serves as the partial dictator of Corollary~\ref{cor:3agents}. Therefore, $F$ allocates a facility to $N_2$ if either $N_2$ is the middle coalition and $y_1 < y_3$, or it is the left or the right coalition.

Therefore, we only need to show that $F$ allocates a facility to the middle coalition $N'_2$ if $N_2 \subset N'_2$, and either $N'_1 \neq N_1$, or $N'_3 \neq N_3$ (or both). To this end, we show how to move agents between the left and the right coalition and from the left and the right coalitions to the middle coalition, and obtain the desired partition $N'_1, N'_2, N'_3$ of agents, while keeping a facility of $F$ allocated to the middle coalition. Then, the lemma follows from Corollary~\ref{cor:3agents}.

For simplicity, we assume that $|N_1| \geq 2$ and that $N_1 \cut N'_1 \neq \emptyset$. We show how to remove these assumptions later on.
%
We first consider the instance $\vec{y}' = (y_1\sep N_1, y_1+\eps\sep N_2, y_3\sep N_3)$, where $\eps > 0$ is chosen small enough that due to $F$'s bounded approximation ratio, the rightmost facility of $F(\vec{y}')$ is placed on the right of $y_1+\eps$. Since $F(\vec{x})$ allocates a facility to $N_2$,  Corollary~\ref{cor:3agents} implies that $y_1+\eps \in F(\vec{y}')$.
%
We observe that as long as there are at least two agents at $y_1$, we can move either some agent $j \in N_1 \cut N'_2$ from $y_1$ to $y_1+\eps$ or some agent $j \in N_1 \cut N'_3$ from $y_1$ to $y_3$, while keeping a facility of $F$ to $y_1+\eps$.
%
More specifically, if an agent $j \in N_1 \cut N'_2$ moves from $y_1$ to $y_1+\eps$, it holds that $y_1+\eps \in F(y_1\sep N_1 \setminus \{ j \}, y_1+\eps\sep N_2 \union \{ j \}, y_3\sep N_3)$, due to $F$'s strategyproofness. Otherwise, agent $j$ in instance $(y_1\sep N_1 \setminus \{ j \}, y_1+\eps\sep N_2 \union \{j\}, y_3\sep N_3)$ could manipulate $F$ by reporting $y_1$ instead of $y_1+\eps$.
%
If an agent $j \in N_1 \cut N'_3$ moves from $y_1$ to $y_3$, it holds that $y_1+\eps \in F(y_1\sep N_1 \setminus \{ j \}, y_1+\eps\sep N_2, y_3\sep N_3 \union \{j\})$, by Corollary~\ref{cor:3agents}. In particular, if the middle coalition is not allocated a facility in $(y_1\sep N_1 \setminus \{ j \}, y_1+\eps\sep N_2, y_3\sep N_3 \union y_3\sep N_3 \union \{j\})$, Corollary~\ref{cor:3agents} implies that the two facilities are placed at $y_1$ and $y_3$. Therefore, agent $j$ in instance $(y_1\sep N_1, y_1+\eps\sep N_2, y_3\sep N_3)$ could manipulate $F$ by reporting $y_3$ instead of $y_1$.
%
By repeatedly applying this argument, we move all agents in $N_1 \cut N'_2$ from the left to the middle coalition and all agents in $N_1 \cut N'_3$ from the left to the right coalition, and keep at least one agent at $y_1$, since $N_1 \cut N'_1 \neq \emptyset$. Thus, we obtain an instance $\vec{z} = (y_1\sep Z_1, y_1+\eps\sep Z_2, y_3\sep Z_3)$ such that $Z_1 = N_1 \cut N'_1 \neq \emptyset$, $Z_2 = N_2 \union (N_1 \cut N'_2)$, $Z_3 = N_3 \union (N_1 \cut N'_3)$, and $y_1+\eps \in F(\vec{z})$. Moreover, since $F$ allocates a facility to the middle coalition $Z_2$ of $\vec{z}$, by Corollary~\ref{cor:3agents}, $F$ allocates a facility to the coalition $Z_2$ for all instances $(y_1\sep Z_1, y\sep Z_2, y_3\sep Z_3)$ with $y_1 < y_3$.

Next, we consider the instance $\vec{z}' = (y_1\sep Z_1, y_3-\eps'\sep Z_2, y_3\sep Z_3)$, where $\eps' > 0$ is chosen small enough that due to $F$'s bounded approximation ratio, the leftmost facility of $F(\vec{z}')$ is located on the left of $y_3-\eps'$. By Corollary~\ref{cor:3agents}, $y_3-\eps' \in F(\vec{z}')$.
%
By an argument symmetric to the argument above, we obtain that as long as there are at least two agents at $y_3$, we can move either some agent $j \in Z_3 \cut N'_2$ from $y_3$ to $y_3-\eps$ or some agent $j \in Z_3 \cut N'_1$ from $y_3$ to $y_1$, while keeping a facility of $F$ to $y_3-\eps'$.
%
As before, by repeatedly applying this argument, we move all agents in $Z_3 \cut N'_2$ from the right to the middle coalition and all agents in $Z_3 \cut N'_1$ from the right to the left coalition. Thus, we obtain the instance $\vec{y}'' = (y_1\sep N'_1, y_3-\eps\sep N'_2, y_3\sep N'_3)$ where $y_3-\eps \in F(\vec{y}'')$.
%
Since $F$ allocates a facility to the middle coalition $N'_2$ of $\vec{y}''$, by Corollary~\ref{cor:3agents}, $F$ allocates a facility to the coalition $N'_2$ for all instances $\vec{y} = (y_1\sep N'_1, y_2\sep N'_2, y_3\sep N'_3)$ with $y_1 < y_3$.

We are now ready to remove the assumptions that $|N_1| \geq 2$ and that $N_1 \cut N'_1 \neq \emptyset$. If $|N_1| = 1$, then $|N_2| \geq 2$, because $|N_2| \leq n-3$, and we start moving agents from $N_3$ (i.e., we first consider the instance $\vec{z}'$ and then the instance $\vec{y}'$). If $N_1 \cut N'_1 = \emptyset$, we first apply two rounds of agent moves between the left and the right coalition, so that every agent in $N'_1 \union (N'_2 \setminus N_2)$ ends up in the left coalition and every agent in $N'_2$ ends up in the right coalition. In a final half-round of agent moves, where we consider only the instance $\vec{y}'$, every agent in $N'_2 \setminus N_2$ moves from the left coalition to the middle coalition. This also deals with the case where $|N'_2| = n-2$.
%
If $y_1 > y_3$, we first work as above and move all agents in $N_1$ from $y_1$ to $y_3$ and all agents in $N_3$ from $y_3$ and $y_1$. Thus, we obtain an instance $(y_3\sep N_1, y_2\sep N_2, y_1\sep N_3)$, with $y_3 < y_1$, and proceed as above.
\qed


\subsection{Details Missing from the Proof of Lemma~\ref{l:unique-dictator-small}}
\label{app:s:unique-dictator-small}

To complete the proof of Lemma~\ref{l:unique-dictator-small}, we have to show that if there is a minimal coalition $N'_2$, $|N'_2| \geq 2$, such that $N'_2$ is a dictator for $3$-location instances, while for every agent $j \in N'_2$, $N'_2 \setminus \{ j \}$ is not a dictator for $3$-location instances, then for any agent $j \in N'_2$ and any agent $i \in N \setminus N'_2$, the coalition $\{ j, i \}$ is a dictator for $3$-location instances.

For sake of a contradiction, we assume that there is an agent $j \in N'_2$ and an agent $i \in N \setminus N'_2$, such that $\{ i, j \}$ is not a dictator for $3$-location instances. For simplicity of notation, we let $C' = N'_2 \setminus \{ j \}$, $C_j = \{j, i\}$, and $N' = N \setminus (C' \union C_j)$. Since the coalition $C_j$ is not a dictator, Lemma~\ref{l:any-partition} implies that for all instances $\vec{x} = (x_1\sep N', x_2\sep C_j, x_3\sep C')$ with $x_1 < x_2 < x_3$, $x_2 \not\in F(\vec{x})$.
%
To reach a contradiction, we consider any such instance $\vec{x}$, and choose a location $r > 2|x_3|+|x_2|$ large enough that for the ($4$-location) instance $\vec{x}' = (\vec{x}_{-i}, r)$, $r \in F(\vec{x}')$. Such an $r$ exists because $F$ has a bounded approximation ratio, and thus every hole in the image set $I_i(\vec{x}_{-i})$ is a bounded interval.

Let $a$ be the location of the other facility of $F(\vec{x}')$. We show that there is no choice of $a$ compatible with the assumption that $F$ is strategyproof, thus obtaining a contradiction.
%
More specifically, if $a = x_2$, the agent $i$ in the instance $\vec{x}$ could manipulate $F$ by reporting $r$ instead of $x_2$.
%
If $a \in (x_2, +\infty)$, the coalition $N'$ in $\vec{x}$ could manipulate $F$ by reporting $x_2$ instead of $x_1$. Then, $\vec{x}_1 = (x_2\sep N' \union \{j\}, x_3\sep C', r\sep \{i\})$ is a $3$-location instance, and since the coalition $C'$ is not a dictator for $3$-location instances, $F_1(\vec{x}_1) = x_2$. Otherwise, by Corollary~\ref{cor:3agents}, $x_3 \in F(\vec{x})$, and thus, by Lemma~\ref{l:any-partition}, $C'$ would be a dictator.
%
If $a \in [-\infty, x_2)$, the coalition $C'$ in $\vec{x}$ could manipulate $F$ by reporting $x_2$ instead of $x_3$. Then, $\vec{x}_2 = (x_1\sep N', x_2\sep N'_2, r\sep \{i\})$ is a $3$-location instance, and since the coalition $N'_2$ is a dictator for $3$-location instances, $x_2 \in F(\vec{x}_2)$.

Therefore, there is an instance $\vec{x} = (x_1\sep N', x_2\sep C_j, x_3\sep C')$, with $x_1 < x_2 < x_3$ and $|C_j| \leq n-3$, such that $x_2 \in F(\vec{x})$. Thus, by Lemma~\ref{l:any-partition}, the coalition $C_j$ is a dictator for $3$-location instances.
\qed


\subsection{The Proof of Lemma~\ref{l:unique-dictator-large}}
\label{app:s:unique-dictator-large}


We distinguish between the case where there exists an instance $\vec{x} = (x_1\sep N_1, x_2\sep N_2, x_3\sep N_3) \in \IthrS(N)$ with $x_1 < x_2 < x_3$, such that $x_2 \in F(\vec{x})$, and the case where for all instances $\vec{y} \in \IthrS(N)$, $F(\vec{y}) = (\min\vec{y}, \max\vec{y})$.

In the former case, Lemma~\ref{l:unique-dictator-small} implies the existence of a unique agent $j \in N_2$ such that for all instances $\vec{y} \in \IthrS(N)$, $y_j \in F(\vec{y})$. Let $i, k \in N$ be any two agents different from $j$. Since the instance $\vec{x}' = (x_1\sep N\setminus\{i,j,k\}, x_2\sep \{ j \}, x_3\sep \{i, k\})$ is a $3$-location instance in $\IthrS(N)$, $x_2 \in F(\vec{x}')$. Moreover, since $x_1 < x_2 < x_3$ and the cardinality of the middle coalition of $\vec{x}'$ is at most $n-3$, Lemma~\ref{l:any-partition} implies that any coalition $N'_2$ that includes $j$ is a dictator for $3$-location instances. Therefore, for all instances $\vec{y} \in \Ithr(N)$, $y_j \in F(\vec{y})$. The uniqueness of such an agent $j$ follows from the bounded approximation ratio of $F$, as in the proof of Lemma~\ref{l:unique-dictator-small}.

In the latter case, for all instances $\vec{y} \in \IthrS(N)$, $F(\vec{y}) = (\min \vec{y}, \max \vec{y})$, and thus instances in $\IthrS(N)$ do not admit a dictator. We next show that for all instances $\vec{y} \in \IthrL(N)$, it is also the case that $F(\vec{y}) = (\min \vec{y}, \max \vec{y})$.
%
For sake of contradiction, let us assume that there is an instance $\vec{z} = (z_1\sep N_1, z_2\sep N_2, z_3\sep N_3) \in \IthrL(N)$ with $z_1 < z_2 < z_3$, such that $F(\vec{z}) \neq (z_1, z_3)$. Thus, by Corollary~\ref{cor:3agents}, $z_2 \in F(\vec{z})$. Since $\vec{z} \in \IthrL(N)$, a coalition has size $n-2$ and the other two coalitions are singletons. If the middle coalition $N_2$ is a singleton, by Lemma~\ref{l:any-partition}, the agent in $N_2$ is a dictator for all $3$-location instances. Otherwise, $|N_2| = n-2$, and Claim~\ref{cl:remove-agent-claim} below implies that for any agent $j \in N_2$, the coalition $N_3 \union \{ j \}$ is a dictator for $3$-location instances. In both cases, we reach a contradiction to the hypothesis that instances in $\IthrS(N)$ do not admit a dictator.

\begin{claim}\label{cl:remove-agent-claim}
Let $N$ be a set of $n \geq 5$ agents. If for all instances $\vec{y} \in \IthrS(N)$, $F(\vec{y}) = (\min\vec{y}, \max\vec{y})$, and there exists an instance $\vec{z} = (z_1\sep N_1, z_2\sep N_2, z_3\sep N_3)$, with $z_1 < z_2 < z_3$ and $N_2 = |n-2|$, such that $z_2 \in F(\vec{z})$, then for any agent $j \in N_2$, the coalition $N_3 \union \{ j \}$ is a dictator for $3$-location instances.
\end{claim}

\begin{proof}[of Claim~\ref{cl:remove-agent-claim}]
The proof is similar to the proof in Section~\ref{app:s:unique-dictator-small}. For simplicity of notation, we let $j \in N_2$ be any agent, let $C' = N_2 \setminus \{ j \}$, let $i$ be the unique agent in $N_1$ and $k$ be the unique agent in $N_3$, and let $C_j = \{ j, k \}$.
%
For sake of contradiction, let us assume that the coalition $C_j$ is not a dictator for $3$-location instances. Therefore, since $|C_j| \leq n-3$, by Lemma~\ref{l:any-partition}, for all instances $\vec{x} = (x_1\sep \{i\}, x_2\sep C_j, x_3\sep C')$, with $x_1 < x_2 < x_3$, $x_2 \not\in F(\vec{x})$.
%
To reach a contradiction, we consider any such instance $\vec{x}$, and choose a location $r > 2|x_3|+|x_2|$ large enough that for the ($4$-location) instance $\vec{x}' = (\vec{x}_{-k}, r)$, $r \in F(\vec{x}')$. Such an $r$ exists because $F$ has a bounded approximation ratio, and thus every hole in the image set $I_k(\vec{x}_{-k})$ is a bounded interval.

Let $a$ be the location of the other facility of $F(\vec{x}')$. We show that there is no choice of $a$ compatible with the assumption that $F$ is strategyproof, thus obtaining a contradiction.
%
More specifically, if $a = x_2$, the agent $k$ in the instance $\vec{x}$ could manipulate $F$ by reporting $r$ instead of $x_2$.
%
If $a \in (x_2, +\infty)$, the agent $i$ in $\vec{x}$ could manipulate $F$ by reporting $x_2$ instead of $x_1$. Then, $\vec{x}_1 = (x_2\sep \{i, j\}, x_3\sep C', r\sep \{k\})$ is a $3$-location instance in $\IthrS(N)$, and by the hypothesis of the claim, $F(\vec{x}_1) = (x_2, r)$.
%
If $a \in [-\infty, x_2)$, the coalition $C'$ in $\vec{x}$ could manipulate $F$ by reporting $x_2$ instead of $x_3$. Then, $\vec{x}_2 = (x_1\sep \{i\}, x_2\sep N_2, r\sep \{k\})$ is a $3$-location instance where $N_1 = \{i\}$ is the left coalition, $N_2$ is the middle coalition, and $N_3 = \{k\}$ is the right coalition. Therefore, by the hypothesis of the claim and Corollary~\ref{cor:3agents}, $x_2 \in F(\vec{x}_2)$.

Hence, there is an instance $\vec{x} = (x_1\sep \{i\}, x_2\sep C_j, x_3\sep C')$, with $x_1 < x_2 < x_3$ and $|C_j| \leq n-3$, such that $x_2 \in F(\vec{x})$. Thus, by Lemma~\ref{l:any-partition}, the coalition $C_j$ is a dictator for $3$-location instances. \qed\end{proof}


%\section{Appendix~\ref{app:2fac-gen}: Details Missing from the Proof of Theorem~\ref{thm:2fac-gen}}
%\label{app:2fac-gen}

%\subsection{Proof of Theorem~\ref{thm:2fac-gen}: Case where $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$}
%\label{app:s:2fac-gen}
